#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:
    """
    @param root: A Tree
    @return: postorder in ArrayList which contains node values.
    """
    def postorderTraversal(self, root):
        self.ret = []

        self.rec_postorder(root)
        # self.non_rec_postorder(root)

        return self.ret

    def non_rec_postorder(self, root):
        self.stack = []
        self.stack.append( [root, 0] )         # 相当于递归首先从root开始遍历
        # self.stack.append(root)         # 相当于递归首先从root开始遍历

        while self.stack:
            node_state = self.stack[-1]
            node, state = node_state
            if not node:
                self.stack.pop()
                continue

            # print(node.val)
            # 判断left, right
            if state == 0:
                self.stack.append([node.left, 0])
                node_state[1] = 1
            elif state == 1:
                self.stack.append([node.right, 0])
                node_state[1] = 2
            else:
                assert state == 2
                self.ret.append(node.val)
                self.stack.pop()

    def rec_postorder(self, node):
        # print('rec')
        if not node:
            return

        # print(node.val)
        # print(self.ret)
        # print(id(self.ret))
        self.rec_postorder(node.left)
        self.rec_postorder(node.right)
        self.ret.append(node.val)


def main():
    print("start main")

    n1 = TreeNode(3)
    n2 = TreeNode(4)
    root = TreeNode(1)
    root.left = n1
    root.right = n2
    s = Solution()
    ret = s.postorderTraversal(root)
    print(ret)

if __name__ == "__main__":
    main()
